Error correcting codes are ubiquitous in communications and data storage systems. Recently considerable interest has grown in a class of codes known as low-density parity-check (LDPC) codes. LDPC codes are provably good codes. On various channels, LDPC codes have been demonstrated to be really close to the channel capacity—the upper limit on transmission rate established by Claude Shannon.
LDPC codes are often represented by bipartite graphs, see exemplary graph 100 of FIG. 1, called Tanner graphs, in which one set of nodes, variable nodes 102, correspond to bits of the codeword and the other set of nodes, constraint nodes 106, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges 104 in the graph 100 connect variable nodes 102 to constraint nodes 106. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. An alternative to the Tanner graph representation of LDPC codes is the parity check matrix representation H 202, FIG. 2. A bit sequence x 206 is a codeword if and only if the product of the bit sequence and H is all-zero, that is: Hx=0.
A bit sequence associated one-to-one with the variable nodes is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
In some cases some of these coded bits might be punctured or known. Punctured bits may be desirable in certain code structures and, in liftings (see below), both punctured and known bits can be used to achieve block lengths that are not multiples of the lifting. Punctured bits and known bits may be, and often are, excluded from the transmitted codeword.
The number of edges attached to a node, i.e., a variable node or constraint node, is referred to as the degree of the node. A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. These were the codes considered originally by Gallager (1961). In contrast to a “regular” code, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
While irregular codes can be more complicated to represent and/or implement, it has been shown that irregular LDPC codes can provide superior error correction/detection performance when compared to regular LDPC codes.
It will be appreciated that received words generated in conjunction with LDPC coding, can be processed by performing LDPC decoding operations thereon, e.g., error correction and detection operations, to generate a reconstructed version of the original codeword. The reconstructed codeword can then be subject to data decoding to recover the original data that was coded. The data decoding process may be, e.g., simply selecting a specific subset of the bits from the reconstructed codeword.
LDPC decoding operations generally comprise message-passing algorithms. There are many potentially useful message-passing algorithms and the use of such algorithms is not limited to LDPC decoding. The principle of a message-passing algorithm is that every node iteratively communicates to its neighbors via the connecting edge about its belief on the bit associated with the edge, the belief of the next iteration depending on the received believes on the current iteration.
Large block length LDPC codes, which correspond to large graph structures, offer many advantages over smaller codes in terms of error resiliency.
To implement a large graph structure using a smaller graph, various permutations may be applied to copies of the smaller graph structure and the copies can be linked together to generate a larger graph structure. In decoding operations, such permutation operations may be implemented by a switching device, referred to herein as a permuter, and also interchangeably referred to as a permutator, which applies a permutation operation on elements, e.g., messages in the case of a decoding operation, as they are passed between a memory and a vector processing unit which performs LDPC operations in parallel.
While various LDPC decoder implementations are known, there remains a need for methods and apparatus which can reduce LDPC decoder hardware implementation costs and/or make an LDPC decoder more flexible in terms of the number of LDPC codes which it can decode and/or the length of codewords which can be decoded by the LDPC decoder.